import math
import random


def assign_cluster(x, centers):
   
    min_dist = float('inf')
    cluster_idx = 0
    for i, c in enumerate(centers):
        
        dist = sum((xi - ci) **2 for xi, ci in zip(x, c))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx


def Kmeans(data, k, epsilon=1e-6, iteration=100):
    
    
    if k <= 0 or k > len(data):
        raise ValueError("k必须是正数且不大于样本数量")
    if len(data) == 0:
        raise ValueError("数据集不能为空")
    
   
    centers = random.sample(data, k)
    n_features = len(data[0])  
    
    for _ in range(iteration):
        
        clusters = [[] for _ in range(k)]  
        labels = []  
        for x in data:
            idx = assign_cluster(x, centers)
            clusters[idx].append(x)
            labels.append(idx)
        
        
        new_centers = []
        for cluster in clusters:
            if not cluster:  
                new_center = random.choice(data)
            else:
                
                new_center = [
                    sum(x[i] for x in cluster) / len(cluster)
                    for i in range(n_features)
                ]
            new_centers.append(new_center)
        
        center_changes = [
            math.sqrt(sum((c1[i] - c2[i])** 2 for i in range(n_features)))
            for c1, c2 in zip(centers, new_centers)
        ]
        if max(center_changes) < epsilon:
            centers = new_centers
            break
        
        centers = new_centers
    
    return centers, labels